package com.le.medium.class3;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

/**
 *给定一个字符串类型的数组arr，求其中出现次数最多的前K个
 * map,堆
 */
public class Problem07_TopKTimes {

    public static class Node{
        String val;
        int times;

        public Node(String val, int times) {
            this.val = val;
            this.times = times;
        }
    }

    public static void printTopKAndRank(String[] arr, int topK){
        if (arr == null || arr.length == 0 || topK < 0){
            return;
        }
        PriorityQueue<Node> heap = new PriorityQueue<>(((o1, o2) -> o2.times - o1.times));
        Map<String,Integer> map = new HashMap<>();

        for (String s : arr) {
            if (map.containsKey(s)){
                map.put(s,map.get(s) + 1);
            }else {
                map.put(s,0);
            }
        }
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        topK = Math.min(arr.length,topK); // 防止topK大于数组长度

        // 1. 维持一个O(n)的大根堆
//        for (Map.Entry<String, Integer> entry : entries) {
//            Node node = new Node(entry.getKey(), entry.getValue());
//            heap.offer(node);
//        }
//        for (int i = 0; i < topK; i++) {
//            System.out.println(heap.poll().val);
//        }
        // 2. 维持一个topK长度的大根堆
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            Node node = new Node(entry.getKey(), entry.getValue());
            if (heap.size() < topK){
                heap.offer(node);
            }else {
                if (node.times > heap.peek().times){
                    heap.poll();
                }
            }
        }
        while (!heap.isEmpty()){
            System.out.println(heap.poll().val);
        }
    }

    @Test
    public void test(){
        String[] arr1 = { "A", "B", "A", "C", "A", "C", "B", "B", "K" };
        printTopKAndRank(arr1, 2);
    }
}
